package org.bridgen.test.compare;

import java.util.ArrayList;

/**
 * 
 * @author Emma Söderberg <emma add cs.lth.se>
 *
 */

public class TreeAlignment {

	private static DistanceFunction df;

	public static int distance(Tree t1, Tree t2, CostFunction cf) {

		// Init stuff
		df = new DistanceFunction(cf);

		// D(@,@) = 0
		Tree.empty().addCachedValue(Tree.empty(),0);
		Forest.empty().addCachedValue(Forest.empty(), 0);

		ArrayList<Tree> t1List = new ArrayList<Tree>();
		t1.postOrderList(t1List);
		ArrayList<Tree> t2List = new ArrayList<Tree>();
		t2.postOrderList(t2List);
//		System.out.println("|T1| = " + t1List.size() + ", |T2| = " + t2List.size());
		
		for (int i = 0; i < t1List.size(); i++) {
			Tree t1v = t1List.get(i);
			df.distance(t1v, Tree.empty());
			df.distance(t1v.forest(), Forest.empty());
		}

		/* DEBUG System.out.println("Initialised T1"); */

		for (int j = 0; j < t2List.size(); j++) {
			Tree t2v = t2List.get(j);
			df.distance(Tree.empty(), t2v);
			df.distance(Forest.empty(), t2v.forest());
		}
		
		/* DEBUG System.out.println("Initialised T2"); */

		for (int i = 0; i < t1List.size(); i++) {
			Tree t1v = t1List.get(i);
			Forest f1v = t1v.forest();
			for (int j = 0; j < t2List.size(); j++) {
				Tree t2v = t2List.get(j);
				Forest f2v = t2v.forest();
				for (int s = 1; s <= f1v.degree(); s++) {
					// Think its OK to check for empty forest here
					if (f2v == Forest.empty()) {
						for (int p = s; p <= f1v.degree(); p++) {
							df.distance(f1v, s, p, Forest.empty());
						}
					} else {
						proc(f1v, s, f1v.degree(), f2v, 1, f2v.degree());
					}
				}
				for (int t = 1; t <= f2v.degree(); t++) {
					// Think its OK to check for empty forest here
					if (f1v == Forest.empty()) {
						for (int q = t; q <= f2v.degree(); q++) {
							df.distance(Forest.empty(), f2v, t, q);
						}
					} else {
						proc(f1v, 1, f1v.degree(), f2v, t, f2v.degree());
					}
				}
				df.distance(t1v, t2v);
			}
		}
		return df.distance(t1, t2);
	}


	// Computes D(F1[i_s,i_p],F2[j_t,j_q]) | s <= p <= m_i, t <= q <= n_j
	private static void proc(Forest f1, int s0, int s, Forest f2, int t0, int t) {

		/*
		 * The intervals correspond to the empty forest
		Forest.Interval f1Int = f1.interval(s0, s0-1);
		Forest.Interval f2Int = f2.interval(t0, t0-1);
		f1.addCachedValue(f1Int, f2Int, 0);
		*/
		// Forest.empty().addCachedValue(Forest.empty(), 0); Unnecessary
		
		for (int p = s0; p <= s; p++) {
			Forest.Interval f1Int = Forest.empty().fullInterval();
			if (s0 <= p) {
				f1Int = f1.interval(s0, p);
			}
			Forest.Interval f2Int = Forest.empty().fullInterval();
			//Forest.Interval f2Int = f2.interval(t0, t0-1); Always the empty forest
			
			if (!f1.hasValueInCacheFor(f1Int, f2Int)) {
				int value = df.distance(f1, s0, p-1, f2, t0, t0-1) + df.distance(f1.tree(p), Tree.empty());
				f1.addCachedValue(f1Int, f2Int, value);
			}
		}

		for (int q = t0; q <= t; q++) {
			Forest.Interval f1Int = Forest.empty().fullInterval();
			//Forest.Interval f1Int = f1.interval(s0, s0-1); Always the empty forest
			Forest.Interval f2Int = Forest.empty().fullInterval();
			if (t0 <= q) {
				f2Int = f2.interval(t0, q);
			}
			
			if (!f1.hasValueInCacheFor(f1Int, f2Int)) {
				int value = df.distance(f1, s0, s0-1, f2, t0, q-1) + df.distance(Tree.empty(), f2.tree(q));
				f1.addCachedValue(f1Int, f2Int, value);
			}
		}

		for (int p = s0; p < s; p++) {
			for (int q = t0; q < t; q++) {
				df.distance(f1, s0, p, f2, t0, q);
			}
		}

		// return .. not needed since calculated values are cached in the tree
	}
}
